package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-06
 * Time:15:40
 */

/**
 * 力扣面试经典150:392. 判断子序列
 * 简单
 * 相关标签
 * 相关企业
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 * 进阶：
 * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
 * 致谢：
 * 特别感谢 @pbrother 添加此问题并且创建所有测试用例。
 * 示例 1：
 * 输入：s = "abc", t = "ahbgdc"
 * 输出：true
 */
public class isSubsequence {
    public static void main(String[] args) {
        isSubsequence("abc","adsbdscd");
    }
    public static boolean isSubsequence(String s, String t) {
//        int lens = s.length();
//        if(lens == 0) return true;
//        int lent = t.length();
//        int indexs = 0;
//        int indext = 0;
//        while(indexs < lens && indext < lent){
//            if(s.charAt(indexs) == t.charAt(indext)){
//                indext++;
//            }
//            if(indext == lent){
//                return true;
//            }
//            indexs++;
//        }
//        return false;
        int n = s.length(); // 获取字符串 s 的长度
        int m = t.length(); // 获取字符串 t 的长度

        // 初始化动态规划数组 f，f[i][j] 表示字符串 t 从位置 i 开始，字符 j 第一次出现的位置
        int[][] f = new int[m + 1][26]; // 26 代表英文字母数量
        for (int i = 0; i < 26; i++) {
            f[m][i] = m; // 初始化为字符串 t 的长度 m
        }

        // 从后往前遍历字符串 t，更新动态规划数组 f
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t.charAt(i) == j + 'a') {
                    f[i][j] = i; // 字符 j 第一次出现的位置是 i
                } else {
                    f[i][j] = f[i + 1][j]; // 否则继承上一个位置的值
                }
            }
        }

        int add = 0; // 初始化指针 add，表示在字符串 t 中的位置
        for (int i = 0; i < n; i++) {
            if (f[add][s.charAt(i) - 'a'] == m) {
                return false; // 如果 s 的字符在 t 中不存在，则 s 不是 t 的子序列
            }
            add = f[add][s.charAt(i) - 'a'] + 1; // 更新指针 add 到下一个位置
        }

        return true; // 遍历完 s 后仍未返回 false，则 s 是 t 的子序列
    }
}
